#include "../../include/common.h"

/*
    递归实现
*/
void PreOrderTraverse_Recursion(BiTree T){
    if (T) {
        PrintBiT(T);                                //调用操作结点数据的函数方法
        PreOrderTraverse_Recursion(T->lchild);      //访问该结点的左孩子
        PreOrderTraverse_Recursion(T->rchild);      //访问该结点的右孩子
    }
    //如果结点为空，返回上一层
    return;
}

/*********************************************************/
/*
    迭代实现：借助栈
*/
int top = -1;
//定义一个顺序栈
BiTree  a[20];

void Push(BiTree* a,BiTree elem)
{
     a[++top]=elem;
}

void Pop()
{
    if (top==-1) {
        return ;
   }
    top--;
}

BiTree GetTop(BiTree*a){
    return a[top];
}


void PreOrderTraverse_Iterative(BiTree Tree)
{
    //临时指针
    BiTree p;
    //根结点进栈
    Push(a, Tree);
    while (top!=-1) {
        //取栈顶元素
        p=GetTop(a);
        //弹栈
        Pop();
        while (p) {
            //调用结点的操作函数
            PrintBiT(p);
            //如果该结点有右孩子，右孩子进栈
            if (p->rchild) {
                Push(a,p->rchild);
            }
            p=p->lchild;//一直指向根结点最后一个左孩子
       }
   }
}


void PreOrderTraverse_Iterative2(BiTree Tree)
{
    BiTree p = Tree;
    while (p || top!=-1) {
        while (p) {
            //调用结点的操作函数
            PrintBiT(p);
            Push(a,p);
            p=p->lchild;//一直指向根结点最后一个左孩子
        }
        if (top!=-1){
            p = GetTop(a);
            Pop();
            p = p->rchild;
        }
    }
}


void run(char* param[]) {
    BiTree Tree;
    CreateBiTree(&Tree);
    printf("先序遍历: \n");
    if (strcmp(param[1], "recursion"))
        PreOrderTraverse_Recursion(Tree);
    else
        PreOrderTraverse_Iterative2(Tree);
   printf("\n\n");
}